package com.lili.divide;

import java.util.concurrent.ThreadLocalRandom;

/**
 * @Auther: 李 力
 * @Date: 2024/8/17
 * @Description: 快速选择算法
 * @version: 1.0
 */
public class QuickSelect {
    /*
     *  求排在第i名的元素，i从0开始，从小到大排
     *   6 5 2 8 9 1
     *   arr数组  left起始位置   right结束位置  第i名
     *
     *   找基准点，比基准点大的放右边，比基准点小的放在左边
     *   时间复杂度 O(n)
     * */
    public static int quickSelect(int[] arr, int left, int right, int i) {
        int partition = partition(arr, left, right);//基准点元素的索引
        if (partition == i) {
            return partition;
        } else if (i < partition) {
            //左边找
            return quickSelect(arr, left, partition - 1, i);
        } else {
            //右边找
            return quickSelect(arr, partition + 1, right, i);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        //优化:随机元素作为基准点元素
        int rand = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(arr, rand, left);
        int pv = arr[left];
        int i = left + 1;
        int j = right;
        //优化:有大量重复的元素
        while (i <= j) {
            //j从右向左找小的
            while (i <= j && arr[i] < pv) {
                i++;
            }
            //i从左向右找大的
            while (i <= j && arr[j] > pv) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        swap(arr, j, left);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
